Each state is denoted by the positions occupied by the letters of the two players in a 3x3 matrix and other empty places.
1. Initial State: An empty 3x3 matrix.
2. Intermediate State: Any arrangement of a 3x3 matrix obtained after applying valid rules on the current state.
3. Final State: Same letters in a complete row or complete column, or complete diagonal wins the game.
4. Rules: The players will get turns one after the other; they can mark their letters on the empty cell.